package org.algorithm.Sort;

public class QuickSort {



    public static void quickSort5(int[]nums,int left,int right){
        if (left < right) {
            int piv = nums[left];
            int currIndex = left + 1;
            int leftIndex = left;
            int rightIndex = right;

            while (currIndex <= rightIndex) {
                if (nums[currIndex] < piv) {
                    swap(nums, currIndex, leftIndex);
                    leftIndex++;
                    currIndex++;
                } else if (nums[currIndex] > piv) {
                    swap(nums, currIndex, rightIndex);
                    rightIndex--;
                } else {
                    currIndex++;
                }
            }

            quickSort5(nums, left, leftIndex - 1);
            quickSort5(nums, leftIndex + 1, right);
        }
    }

    public static void main(String[] args) {
        int[] nums = {3, 6, 8, 10, 1, 2, 1};
        quickSort5(nums, 0, nums.length-1);
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }

    }


    // Deprecated----------------------------------------------------------------------------
    private static void QuickSort3Ways3(int [] arr ,int left, int right){
        if (left>=right){
            return;
        }

        int v = arr[left];
        int lt = left;
        int gt = right+1;

        int curr = left+1;

        while (curr<gt){
            if (arr[curr]<v){
                swap(arr,curr,lt+1);
                curr++;
                lt++;
            }else if (arr[curr]>v){
                swap(arr,curr,gt-1);
                gt--;
            }else {
                curr++;
            }
        }
        swap(arr,lt,left);

        QuickSort3Ways3(arr,left,lt-1);
        QuickSort3Ways3(arr,gt,right);

    }


    //三路递归
    private static void QuickSort3Ways2(int [] arr ,int left, int right){

        if (left>=right){
            return;
        }

        //基准值
        int v = arr[left];

        //小于v区间的右边界
        int lt = left;
        //大于v区间的左边界
        int gt = right+1;

        //遍历的下标
        int i = left+1;

        while (i<gt){

            if (arr[i]<v){
                swap(arr,i,lt+1);
                i++;
                lt++;
            }else if (arr[i]>v){
                swap(arr,i,gt-1);
                gt--;
            }else {
                i++;
            }
        }
        //将基准值与小于v区间的右边界的值进行交换
        swap(arr,left,lt);

        //只需要将小于v和大于v的区间进行处理
        QuickSort3Ways2(arr,left,lt-1);
        QuickSort3Ways2(arr,gt,right);

    }

    private static void QuickSort3Ways(int[] arr, int l, int r){

        if (l >= r) {
            return;
        }

        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        swap( arr, l, (int)(Math.random()*(r-l+1)) + l );

        int v = arr[l];

        int lt = l;     // arr[l+1...lt] < v
        int gt = r + 1; // arr[gt...r] > v
        int i = l+1;    // arr[lt+1...i) == v
        while( i < gt ){
            if( arr[i] < v){
                swap( arr, i, lt+1);
                i ++;
                lt ++;
            }
            else if( arr[i] > v ){
                swap( arr, i, gt-1);
                gt --;
            }
            else{ // arr[i] == v
                i ++;
            }
        }

        swap( arr, l, lt );

        QuickSort3Ways(arr, l, lt-1);
        QuickSort3Ways(arr, gt, r);
    }

    private static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }


    //错误
    public static void quickSort3(int [] nums,int left ,int right){

        if (left<right){
            return;
        }

        int pv = nums[left];
        int i = left+1;
        int j = right;

        int temp;

        while (i<=j){

            while (i<=j && nums[i]<pv){
                i++;
            }

            while (i<=j && pv<nums[j]){
                j--;
            }

            if (i<=j){
                temp=nums[i];
                nums[i]=nums[j];
                nums[j]=temp;
                i++;
                j--;
            }
        }

        nums[left]=nums[j];
        nums[j]=pv;

        quickSort3(nums,left,i-1);
        quickSort3(nums,i+1,right);

    }


    //快速排序
    public static void quickSort2(int [] nums,int left ,int right){
        if (left>right){
            return;
        }

        int pv = nums[left];
        int i = left;
        int j = right;
        int temp;

        while (i<j){
            //先判断右边
            while (i<j && pv<nums[j]){
                j--;
            }
            //再判断左边
            while (i<j && pv>=nums[i]){
                i++;
            }

            //运行到此处说明nums[j]遇到了比pv小的值，num[i]遇到了比pv大的值，需要交换左右两个数
            if (i<j){
                temp=nums[i];
                nums[i]=nums[j];
                nums[j]=temp;
            }

        }

        //将i和j相遇的数与pv进行交换
        nums[left]=nums[i];
        nums[i]=pv;

        quickSort2(nums,left,i-1);
        quickSort2(nums,i+1,right);

    }




    public static void quickSort(int [] nums ,int low ,int high){
        int i,j,temp,t;

        if (low>high){
            return;
        }

        i=low;
        j=high;

        temp=nums[low];

        while (i<j){

            while (temp<=nums[j] && i<j){
                j--;
            }

            while (temp>=nums[i] && i<j){
                i++;
            }

            if (i<j){
                t=nums[j];
                nums[j]=nums[i];
                nums[i]=t;
            }
        }

        nums[low]=nums[i];
        nums[i]=temp;

        quickSort(nums,low,j-1);

        quickSort(nums,j+1,high);
    }


}
